/*
 * @Author: szx
 * @Date: 2022-05-17 13:13:18
 * @LastEditTime: 2022-05-17 13:28:45
 * @Description:
 * @FilePath: \leetcode\面试题\04\01\01.js
 */
/**
 * @param {number} n
 * @param {number[][]} graph
 * @param {number} start
 * @param {number} target
 * @return {boolean}
 */
var findWhetherExistsPath = function (n, graph, start, target) {
    if (target >= n) return false;
    // 构建映射关系表
    const map = {};
    for (const g of graph) {
        const x = g[0],
            y = g[1];
        if (map[x] === undefined) map[x] = [];
        if (!map[x].includes(y)) map[x].push(y);
    }
    const vis = new Array(n).fill(false);
    const dfs = (index) => {
        if (index == target) return true;
        if (vis[index]) return false;
        vis[index] = true;
        const to = map[index];
        if (to == undefined) return false; // 没有可去的点了，无法到达，返回false
        for (let i = 0; i < to.length; i++) {
            if (dfs(to[i])) return true; // 递归进入下一层
        }
        return false;
    };
    return dfs(start);
};

var findWhetherExistsPath = function (n, graph, start, target) {
    if (target >= n) return false;
    // 构建映射关系表
    const map = {};
    for (const g of graph) {
        const x = g[0],
            y = g[1];
        if (map[x] === undefined) map[x] = [];
        if (!map[x].includes(y)) map[x].push(y);
    }
    const vis = new Array(n).fill(false);
    const que = [start];

    while (que.length) {
        const index = que.pop();
        if (index == target) return true;
        if (vis[index]) continue;
        vis[index] = true;
        const to = map[index];
        if (to == undefined) return false;
        for (let i = 0; i < to.length; i++) {
            que.push(to[i]);
        }
    }
    return false;
};
